#include <stdio.h>
#include <stdlib.h>

// 栈：先进后出

// 栈存储数据的结构
typedef struct Node
{
    int num;
    struct Node* next;
}NODE;

// 管理栈的结构
typedef struct myStack
{
    struct Node* top; // 记录当前栈中最后一个数据的地址(栈顶指针)
    int count;        // 记录栈中的数据个数
}STACK;


// 初始化栈
STACK* stack_init()
{
    STACK* ptr = (STACK*)malloc(sizeof(STACK));
    if (ptr == NULL)
    {
        perror("statck init fail");
        return NULL;
    }

    ptr->top = NULL;
    ptr->count = 0;

    return ptr;
}

// 向栈中压入一个数据，也称之为入栈
void statck_push(STACK* s, int data)
{
    NODE* d = (NODE*)malloc(sizeof(NODE));
    if (d == NULL)
    {
        perror("data malloc fail");
        return;
    }
    d->num = data;

    d->next = s->top; // 用于链表栈中的每一个数据

    s->top = d;       // 栈顶指针，始终指向栈中最上面的元素

    (s->count)++;
}

// 从栈中取出一个数据，出栈
void statck_pop(STACK* s, int* data)
{
    if (s->top == NULL)
    {
        return;
    }

    NODE* p = s->top;       // 记录栈顶元素的地址
 
    s->top = s->top->next;  // 将栈顶指针下移

    *data = p->num; // 记录将要出栈的数据

    free(p);
    p = NULL;

    (s->count)--;
}

void statck_display(STACK* s)
{
    NODE* p1 = s->top;

    while(p1 != NULL)
    {
        printf("%d --> ", p1->num);
        p1 = p1->next;
    }
    printf("已到栈底\n");
}

int main(int argc,char *argv[])
{
    STACK* s = stack_init();

    statck_push(s, 1);
    statck_push(s, 2);
    statck_push(s, 3);
    statck_push(s, 4);
    statck_push(s, 5);

    statck_display(s);

    int data;
    statck_pop(s, &data);
    statck_display(s);

    statck_pop(s, &data);
    statck_display(s);

    statck_pop(s, &data);
    statck_display(s);

    statck_pop(s, &data);
    statck_display(s);

    statck_pop(s, &data);
    statck_display(s);

    return 0;
}
